A provider may host a distributed database management system on behalf of various clients. The provider may limit utilization of the computing nodes that make up the database management system for various reasons, such as providing a minimum quality-of-service level. To do so, the provider may provision a certain amount of computing capacity to each client, and limit operations that may be performed on behalf of a client once that amount has been exceeded. This approach may rely on a means of estimating the amount of computing capacity that would be consumed by performing an operation on behalf of the client. Certain measures of capacity utilization, such as input/output utilization, are useful for this purpose because they may be readily ascertained.